package mine.code.day.year2021.month08;

import org.junit.Test;

import java.util.Arrays;

/**
 * 有 n 个城市通过一些航班连接。给你一个数组flights ，其中flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。
 * <p>
 * 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k站中转的路线，使得从 src 到 dst 的 价格最便宜 ，
 * 并返回该价格。
 * 如果不存在这样的路线，则输出 -1。
 * <p>
 * 示例 1：
 * <p>
 * 输入:
 * n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
 * src = 0, dst = 2, k = 1
 * 输出: 200
 * 解释:
 * <p>
 * 从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200
 * <p>
 * 示例 2：
 * <p>
 * 输入:
 * n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
 * src = 0, dst = 2, k = 0
 * 输出: 500
 *
 * @author caijinnan
 */
public class _Undone_Day24_K站中转内最便宜的航班 {

    @Test
    public void run() {
        int n = 3;
        int[][] edges = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}};
        int src = 0, dst = 2, k = 1;
        System.out.println(findCheapestPrice(n, edges, src, dst, k));
    }


    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // dp[k][j] = min(dp[k-1][j]+cost(j,dst))
        int[][] dp = new int[k + 1][dst + 1];
        dp[0][src] = 0;
        for (int[] temp : dp) {
            Arrays.fill(temp, Integer.MAX_VALUE);
        }
        for (int numK = 1; numK <= k; numK++) {
            for (int transit = src + 1; transit <= dst; transit++) {
                dp[numK][transit] = minCost(dp, transit, numK, flights, src);
            }
        }
        return dp[k][dst] == Integer.MAX_VALUE ? -1 : dp[k][dst];
    }

    private int minCost(int[][] dp, int transit, int numK, int[][] flights, int src) {
        int minCost = Integer.MAX_VALUE;
        for (int i = src; i <= transit; i++) {
            minCost = Math.min(minCost, cost(dp[numK - 1][i], i, transit, flights));
        }

        return minCost;
    }

    private int cost(int lastCost, int i, int transit, int[][] flights) {
        for (int[] flight : flights) {
            if (flight[0] == i && flight[1] == transit) {
                return flight[2] + lastCost;
            }
        }
        return Integer.MAX_VALUE;
    }
}
